package com.future;

import java.util.Arrays;

/**
 * Description: 1575. 统计所有可行路径
 * 示例 1：
 * <p>
 * 输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
 * 输出：4
 * 解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
 * 1 -> 3
 * 1 -> 2 -> 3
 * 1 -> 4 -> 3
 * 1 -> 4 -> 2 -> 3
 * 示例 2：
 * <p>
 * 输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
 * 输出：5
 * 解释：以下为所有可能的路径：
 * 1 -> 0，使用汽油量为 fuel = 1
 * 1 -> 2 -> 0，使用汽油量为 fuel = 5
 * 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
 * 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
 * 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
 * <p>
 * @author weiruibai.vendor
 * Date: 2023/2/20 09:57
 */
public class Solution_1575 {

    private static Solution_1575 instance = new Solution_1575();

    public static void main(String[] args) {
        int[] locations = new int[]{4, 3, 1};
        int start = 1;
        int finish = 0;
        int fuel = 6;
        System.out.println(instance.countRoutes(locations, start, finish, fuel));
    }

    int mod = 1000000007;

    // 缓存器：用于记录「特定状态」下的结果
    // cache[i][fuel] 代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置的「路径数量」
    int[][] cache;

    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;

        // 初始化缓存器
        // 之所以要初始化为 -1
        // 是为了区分「某个状态下路径数量为 0」和「某个状态尚未没计算过」两种情况
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }

        int ans = dfs(ls, start, end, fuel);
        return ans;
    }

    /**
     * 解析可参考：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485297&idx=1&sn=5ee4ce31c42d368af0653f60aa263c82&chksm=fd9cac6ecaeb25787e6da90423c5467e1679da0a8aaf1a3445475199a8f148d8629e851fea57&scene=178&cur_album_id=1773144264147812354#rd
     * 计算「路径数量」
     *
     * @param ls          入参 locations
     * @param curIndex    当前所在位置（ls 的下标）
     * @param targetIndex 目标哦位置（ls 的下标）
     * @param fuel        剩余油量
     * @return 在位置 curIndex 出发，油量为 fuel 的前提下，到达 targetIndex 的「路径数量」
     */
    int dfs(int[] ls, int curIndex, int targetIndex, int fuel) {
        // 如果缓存器中已经有答案，直接返回
        if (cache[curIndex][fuel] != -1) {
            return cache[curIndex][fuel];
        }
        int n = ls.length;
        int sum;
        // base case 1：如果油量为 0，且不在目标位置
        // 将结果 0 写入缓存器并返回
        if (fuel == 0 && curIndex == targetIndex) {
            sum = 1;
        } else {
            // base case 2：油量不为 0，且无法到达任何位置
            // 将结果 0 写入缓存器并返回
            // 计算油量为 fuel，从位置 curIndex 到 targetIndex 的路径数量
            // 由于每个点都可以经过多次，如果 curIndex = targetIndex，那么本身就算一条路径
            sum = curIndex == targetIndex ? 1 : 0;
            for (int i = 0; i < n; i++) {
                if (i != curIndex) {
                    int need = Math.abs(ls[i] - ls[curIndex]);
                    if (fuel >= need) {
                        sum += dfs(ls, i, targetIndex, fuel - need);
                        sum %= mod;
                    }
                }
            }

        }
        cache[curIndex][fuel] = sum;
        return sum;
    }
}

